A semantic graph can be formulated in which nodes represent concepts and edges represent probabilistic assertions pertaining to the concepts. For example, such a graph may include a first node pertaining to the concept of “Seattle” a second node pertaining to concept of “Specialist XYZ.” An edge connecting these two nodes can identify the probability that Seattle is home to at least one doctor who is a specialist in field XYZ.
In addition to the knowledge that is directly conveyed by individual edges, a user may attempt to perform probabilistic reasoning over multiple edges in the semantic graph. However, present-day technology does not provide efficient mechanisms for performing this task. Indeed, present-day solutions quickly become intractable with an increase in the number of edges under consideration.